package problems.daily;

import java.util.HashMap;

/**
 * 927. 三等分
 * <p>https://leetcode.cn/problems/three-equal-parts/</p>
 *
 * @author habitplus
 * @since 12:09, 2022/10/6
 */
public class DT927 {
    /**
     * 三指针
     */
    public int[] threeEqualParts(int[] arr) {
        if (arr == null || arr.length < 3) return new int[]{-1, -1};

        int n = arr.length;

        // 记录 1 总数
        int oneCnt = 0;
        for (int a : arr) oneCnt += a;

        if (oneCnt % 3 != 0) return new int[]{-1, -1};
        if (oneCnt == 0) return new int[]{0, n - 1};

        // 分成三组，每组相同个数 1
        // first 指向第一组首个 1 的下标
        // second 指向第二组首个 1 的下标
        // three 指向第三组首个 1 的下标
        int first = find(arr, 1);
        int second = find(arr, oneCnt / 3 + 1);
        int three = find(arr, oneCnt / 3 * 2 + 1);

        int n1 = second;
        int n2 = three;

        // 去掉前导零，第三组可以唯一确定的
        while (three < n) {
            if (first >= n1 || second >= n2) break;

            if (arr[first] == arr[three] && arr[second] == arr[three]) {
                ++first;
                ++second;
                ++three;
            }
            else break;
        }

        return three == n ? new int[]{first, second} : new int[] {-1, -1};
    }

    private int find(int[] arr, int no) {
        for (int i = 0; i < arr.length; ++i) {
            no -= arr[i];
            if (no == 0) return i;
        }
        return 0;
    }


    public int[] threeEqualParts1(int[] arr) {
        if (arr == null || arr.length < 3) return new int[]{-1, -1};

        int n = arr.length;

        // 记录 1 的位置 和 总数
        int oneCnt = 0;
        HashMap<Integer, Integer> indexOneMap = new HashMap<>();

        StringBuilder str = new StringBuilder();

        for (int i = 0; i < n; ++i) {
            str.append(arr[i]);
            if (arr[i] == 1) {
                ++oneCnt;
                indexOneMap.put(oneCnt, i);
            }
        }

        if (oneCnt % 3 != 0) return new int[]{-1, -1};
        if (oneCnt < 1) return new int[]{0, n - 1};

        int l1 = indexOneMap.getOrDefault(oneCnt / 3, 0);
        int r1 = indexOneMap.getOrDefault(oneCnt / 3 + 1, 0);
        int l2 = indexOneMap.getOrDefault(oneCnt / 3 * 2, 0);
        int r2 = indexOneMap.getOrDefault(oneCnt / 3 * 2 + 1, 0);

        int first = indexOneMap.getOrDefault(1, 0);
        String a, b, c;

        c = str.substring(r2);

        // 枚举第一个位置 [l1, r2);
        for (int one = l1; one < r1; ++one) {
            a = str.substring(first, one + 1);
            if (a.equals(c)) {
                // 枚举第二个位置 (l2, r2]
                for (int two = l2 + 1; two <= r2; ++two) {
                    b = str.substring(r1, two);
                    if (a.equals(b))
                        return new int[]{one, two};
                }
            }
        }

        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        System.out.println((0 % 3));
    }
}
